Матч 322, Групповая работа (GroupWork)

Дивизион 2, Уровень 2

Имеются группы людей, которые выполняют работу с определенной производительностью В i - ой группе находится p[i] людей, уровень производительности каждого человека этой группы равен s[i].

Продуктивность работы группы из k человек равна k * x, где x – наименьший уровень производительности у человека из этой группы. Имея размеры групп p и производительности людей в группах s, необходимо составить такую группу, продуктивность работы которой будет наибольшей.

Класс: GroupWork

Метод: long long bestGroup(vector<int> p, vector<int> s)

Ограничения: p содержит от 1 до 50 элементов, s и p содержат одинаковое количество элементов, 1 £ p[i] £ 10⁹, 1 £ s £ 1000.

Вход. Массив размеров групп людей p и массив уровней мастерства s.

Выход. n - ая разность последовательности a.

Пример входа

p	s
{1,2,1}	{3,5,9}
{2,2,2,2}	{5,1,1,5}
{1000000000,1000000000,1000000000}	{1000,999,998}

Пример выхода

15

20

2994000000000

РЕШЕНИЕ

жадный алгоритм

Составим вектор v пар (s[i], p[i]) и отсортируем его по убыванию производительности, то есть по первой компоненте. Будем последовательно включать в рабочую группу людей по убыванию их производительности. Для каждой текущей группы ищем ее продуктивность работы, и среди всех продуктивностей находим наибольшую.

Пусть (s[0], p[0]), (s[1], p[1]), …, (s[n], p[n]) – вектор v, отсортированный по убыванию первой компоненты. i - ой будем называть группу, состоящую из p[0] + p[1] + … + p[i] людей, 0 £ i £ v.size(). Наименьший уровень производительности i - ой группы равен s[i]. Поэтому ее производительность равна (p[0] + p[1] + … + p[i]) * s[i]. Искомая максимальная продуктивность равна

ПРОГРАММА

#include <cstdio>

#include <vector>

#include <algorithm>

#include <functional>

using namespace std;

class GroupWork

{

public:

long long bestGroup(vector<int> p, vector<int> s)

{

vector<pair<int,int> > v;

long long res, i, people;

for(i = 0; i < p.size(); i++) v.push_back(make_pair(s[i],p[i]));

sort(v.begin(),v.end(),greater<pair<int,int> >());

for(people = res = i = 0; i < v.size(); i++)

{

people += v[i].second;

if (res < people * v[i].first) res = people * v[i].first;

}

return res;

}

};